﻿
Imports osi.root.connector

Partial Public Class bt(Of T)
    Protected root As node

    Public Shared Function move(ByVal v As bt(Of T)) As bt(Of T)
        If v Is Nothing Then
            Return Nothing
        Else
            Dim r As bt(Of T) = Nothing
            r = New bt(Of T)()
            move_to(v, r)
            Return r
        End If
    End Function

    Protected Shared Sub move_to(ByVal from As bt(Of T), ByVal [to] As bt(Of T))
        k_assert(Not from Is Nothing)
        k_assert(Not [to] Is Nothing)
        [to].root = from.root
        from.root = Nothing
    End Sub

    'make sure the tree from root <r> is not a graph
    Private Shared Sub assert_structure(ByVal r As node, ByVal v As vector(Of node))
        k_assert(Not r Is Nothing)
        k_assert(Not v Is Nothing)
        For i As UInt32 = 0 To v.size() - 1
            k_assert(object_compare(v(i), r) <> 0)
        Next
        v.emplace_back(r)
        If r.has_left_child() Then
            assert_structure(r.left_child(), v)
        End If
        If r.has_right_child() Then
            assert_structure(r.right_child(), v)
        End If
    End Sub

    Protected Shared Sub assert_structure(ByVal r As node)
        k_assert(Not r Is Nothing)
        Dim v As vector(Of node) = Nothing
        v = New vector(Of node)()
        assert_structure(r, v)
    End Sub

    Public Function [end]() As iterator
        Return iterator.end
    End Function

    Public Function rend() As iterator
        Return iterator.end
    End Function

    Public Function begin() As iterator
        Return If(empty(), [end](), New iterator(root.min()))
    End Function

    Public Function rbegin() As iterator
        Return If(empty(), rend(), New iterator(root.max()))
    End Function

    Public Function size() As UInt32
        Return If(empty(), 0, root.subtree_node_count())
    End Function

    Public Function count() As UInt32
        Return size()
    End Function

    Public Function empty() As Boolean
        Return root Is Nothing
    End Function

    Public Sub clear()
        root = Nothing
    End Sub
End Class
